package Solution201_220;

public class Solution215 {
    public int findKthLargest(int[] nums, int k) {
        for(int i=0;i<nums.length;i++){
            k--;
            for(int j=i+1;j<nums.length;j++){
                if(nums[j]>nums[i]){
                    swap(nums,i,j);
                }
            }
            if(k==0){
                return nums[i];
            }
        }
        return -1;
    }

    private void swap(int[] nums,int start,int end){
        int temp=nums[start];
        nums[start]=nums[end];
        nums[end]=temp;
    }


    //采用二个指针的快速排序
    public int findKthLargestBest(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1 || k > nums.length){
            return -1;
        }
        return partition(nums, 0, nums.length - 1, nums.length - k);
    }

    private int partition(int[] nums, int start, int end, int k){
        //if (start >= end){
        //return nums[k];
        //}

        int left = start;
        int right = end;
        int pivot = nums[(start + end) / 2];

        while(left <= right){
            while (left <= right && nums[left] < pivot) {
                left++;
            }
            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }

        if (k <= right) {
            return partition(nums, start, right, k);
        }

        if (k >= left) {
            return partition(nums, left, end, k);
        }
        return nums[k];

    }
}
